package com.cet.qz.unit01.chapter1_3;

import java.util.Iterator;

/**
 * @program: algorithm
 * @description:
 * @author: 陈恩涛
 * @create: 2021-03-28 21:26
 **/
public class QueueImplBylLink {
    public static void main(String[] args) {
        Queue<Integer> integers = new Queue<>();
        integers.enqueue(1);
        integers.enqueue(2);
        integers.enqueue(3);
        integers.enqueue(4);
        System.out.println(integers.dequeue());
        System.out.println("============");
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }
}

class Queue<Item> implements Iterable<Item> {


    private class Node {
        private Item item;
        private Node next;
    }

    private Node first; //队首
    private Node last; //队尾
    private int N; //队列中元素的个数



    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;
    }

    public void enqueue(Item item) {
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty()) {
            first = last;
        } else {
            oldlast.next = last;
        }
        N++;
    }

    public Item dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空！");
        }
        Item item = first.item;
        first = first.next;
        if (isEmpty()) {
            last = null;
        }
        N--;
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new LinkedIterator(first);
    }

    class LinkedIterator implements Iterator<Item> {

        private Node firstNode;

        public LinkedIterator(Node firstNode) {
            this.firstNode = firstNode;
        }

        @Override
        public boolean hasNext() {
            return firstNode != null;
        }

        @Override
        public Item next() {
            if (!hasNext()) {
                throw new RuntimeException("队列为空!");
            }
            Item item = firstNode.item;
            firstNode = firstNode.next;
            return item;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

}
